// win_hash_map.h

#ifndef _win_hash_map_h_
#define _win_hash_map_h_

#if _MSC_VER > 1000
	#pragma once
#endif

#if !defined(_MSC_VER)
	#error only for VC
#endif

#include <xmemory>
#include <iterator>
#include <new>
#include <utility>
#include <vector>
#include <functional>

#ifdef _STLPORT_VERSION
	#error stlport used!
#endif

#pragma pack(push,8)

#pragma warning(push)
#pragma warning(disable: 4702)	/* unreachable code */
#pragma warning(disable: 4355 4284  4231 4511 4512 4097 4786 4800 4018 4146 4244 4514 4127 4100 4663)
#pragma warning(disable: 4245 4514 4660)
#pragma warning(error: 4035)	/* 'function' : no return value */

#define _STL_NAMESPACE std

#if _STL_NAMESPACE != std

namespace _STL_NAMESPACE {
	using ::ptrdiff_t;
	using ::size_t;
	using std::pair;
	using std::input_iterator_tag;
	using std::forward_iterator_tag;
	using std::random_access_iterator_tag;
	using std::unary_function;
	using std::vector;
	using std::less;
	using std::distance;
	using std::advance;
	using std::allocator;
} // end of namespace _STL_NAMESPACE

#endif // _STL_NAMESPACE != std


namespace _STL_NAMESPACE {
	template <class _Tp>
		struct _Nonconst_traits;
	template <class _Tp>
		struct _Const_traits {
		typedef _Tp value_type;
		typedef const _Tp&  reference;
		typedef const _Tp*  pointer;
		typedef _Nonconst_traits<_Tp> _Non_const_traits;
	};
	template <class _Tp>
		struct _Nonconst_traits {
		typedef _Tp value_type;
		typedef _Tp& reference;
		typedef _Tp* pointer;
		typedef _Nonconst_traits<_Tp> _Non_const_traits;
	};

	template <class _Tp1, class _Tp2>
		inline allocator<_Tp2>& __cdecl
		__stl_alloc_rebind(allocator<_Tp1>& __a, const _Tp2*) {  return (allocator<_Tp2>&)(__a); }

	template <class _Value, class _Tp, class _MaybeReboundAlloc>
		class _STLP_alloc_proxy : public _MaybeReboundAlloc {
	private:
		typedef _MaybeReboundAlloc _Base;
		typedef _STLP_alloc_proxy<_Value, _Tp, _MaybeReboundAlloc> _Self;
	public:
		_Value _M_data;
		inline _STLP_alloc_proxy(const _MaybeReboundAlloc& __a, _Value __p) : _MaybeReboundAlloc(__a), _M_data(__p) {}
		inline _Tp* allocate(size_t __n) {
			return __stl_alloc_rebind(static_cast<_Base&>(*this),(_Tp*)0).allocate(__n,0);
		}
		inline void deallocate(_Tp* __p, size_t __n) {
			__stl_alloc_rebind(static_cast<_Base&>(*this),(_Tp*)0).deallocate(__p, __n);
		}
	};

	template <class _Pair>
		struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> {
		const typename _Pair::first_type& operator()(const _Pair& __x) const
			{	return __x.first;	}
	};

	template <class _Tp>
		struct _Identity : public unary_function<_Tp,_Tp> {
		const _Tp& operator()(const _Tp& __x) const { return __x; }
	};

	template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
		_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
		const _Tp& __val, _Compare __comp, _Distance*)
	{
		_Distance __len = distance(__first, __last);
		_Distance __half;
		_ForwardIter __middle;
		while (__len > 0) {
			__half = __len >> 1;
			__middle = __first;
			advance(__middle, __half);
			if (__comp(*__middle, __val)) {
				__first = __middle;
				++__first;
				__len = __len - __half - 1;
			}
			else
				__len = __half;
		}
		return __first;
	}

	template <class _Tp>
		less<_Tp> __less(_Tp* ) { return less<_Tp>(); }

//	template <class _T1, class _T2>
//		inline void _Construct(_T1* __p, const _T2& __val) {
//		new (__p) _T1(__val);
//	}

//	template <class _Tp>
//		inline void _Destroy(_Tp* __pointer) {
//		__pointer->~_Tp();
//	}
} // end of namespace _STL_NAMESPACE

namespace _STL_NAMESPACE {
	template <class _Key> struct hash { };
	inline size_t __stl_hash_string(const char* __s)
	{
		unsigned long __h = 0;
		for ( ; *__s; ++__s)
			__h = 5*__h + *__s;
		return size_t(__h);
	}
	template<> struct hash<char*>
	{
		size_t operator()(const char* __s) const {  return __stl_hash_string(__s); }
	};
	template<> struct hash<const char*>
	{
		size_t operator()(const char* __s) const {  return __stl_hash_string(__s); }
	};
	inline size_t __stl_hash_string(const wchar_t* __s)
	{
		unsigned long __h = 0;
		for ( ; *__s; ++__s)
			__h = 5*__h + *__s;
		return size_t(__h);
	}
	template<> struct hash<wchar_t*>
	{
		size_t operator()(const wchar_t* __s) const {  return __stl_hash_string(__s); }
	};
	template<> struct hash<const wchar_t*>
	{
		size_t operator()(const wchar_t* __s) const {  return __stl_hash_string(__s); }
	};
	template<> struct hash<char> {
		size_t operator()(char __x) const { return __x; }
	};
	template<> struct hash<unsigned char> {
		size_t operator()(unsigned char __x) const { return __x; }
	};
	template<> struct hash<signed char> {
		size_t operator()(unsigned char __x) const { return __x; }
	};
	template<> struct hash<short> {
		size_t operator()(short __x) const { return __x; }
	};
	template<> struct hash<unsigned short> {
		size_t operator()(unsigned short __x) const { return __x; }
	};
	template<> struct hash<int> {
		size_t operator()(int __x) const { return __x; }
	};
	template<> struct hash<unsigned int> {
		size_t operator()(unsigned int __x) const { return __x; }
	};
	template<> struct hash<long> {
		size_t operator()(long __x) const { return __x; }
	};
	template<> struct hash<unsigned long> {
		size_t operator()(unsigned long __x) const { return __x; }
	};
	template<> struct hash<__int64> {
		size_t operator()(long x) const { return x; }
	};
	template<> struct hash<unsigned __int64> {
		size_t operator()(unsigned long x) const { return x; }
	};
} // end of namespace _STL_NAMESPACE

namespace _STL_NAMESPACE {
	template <class _Val>
		struct _Hashtable_node
	{
		typedef _Hashtable_node<_Val> _Self;
		_Self* _M_next;
		_Val _M_val;
	};

	template <class _Val, class _Key, class _HF,
		class _ExK, class _EqK, class _All>
		class hashtable;

	template <class _Val, class _Key, class _HF,
		class _ExK, class _EqK, class _All>
		struct _Hashtable_iterator
	{
		typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
			_Hashtable;
		typedef _Hashtable_node<_Val> _Node;
		_Node* _M_cur;
		_Hashtable* _M_ht;
		_Hashtable_iterator(_Node* __n, _Hashtable* __tab)
			: _M_cur(__n), _M_ht(__tab) {}
		_Hashtable_iterator() {}
		_Node* _M_skip_to_next();
	};

	template <class _Val, class _Traits, class _Key, class _HF,
		class _ExK, class _EqK, class _All>
		struct _Ht_iterator : public _Hashtable_iterator< _Val, _Key,_HF, _ExK,_EqK,_All>
	{
		typedef _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> _Base;
		typedef _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All> _Self;
		typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> _Hashtable;
		typedef _Hashtable_node<_Val> _Node;
		typedef _Val value_type;
		typedef forward_iterator_tag iterator_category;
		typedef ptrdiff_t difference_type;
		typedef size_t size_type;
		typedef typename _Traits::reference reference;
		typedef typename _Traits::pointer   pointer;
		_Ht_iterator(const _Node* __n, const _Hashtable* __tab) :
		_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>((_Node*)__n, (_Hashtable*)__tab) {}
		_Ht_iterator() {}
		_Ht_iterator(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __it) :
		_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>(__it) {}
		reference operator*() const {
			return this->_M_cur->_M_val;
		}
		pointer operator->() const { return &(operator*()); }
		_Self& operator++() {
			_Node* __n = this->_M_cur->_M_next;
			this->_M_cur =  (__n !=0 ? __n : this->_M_skip_to_next());
			return *this;
		}
		inline  _Self operator++(int) {
			_Self __tmp = *this;
			++*this;
			return __tmp;
		}
	};

	template <class _Val, class _Traits, class _Traits1, class _Key, class _HF,
		class _ExK, class _EqK, class _All>
		inline bool
		operator==(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>& __x,
		const _Ht_iterator<_Val, _Traits1,_Key,_HF,_ExK,_EqK,_All>& __y) {
		return __x._M_cur == __y._M_cur;
	}

	template <class _Val, class _Key, class _HF,
		class _ExK, class _EqK, class _All>
		inline bool
		operator!=(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __x,
		const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __y) {
		return __x._M_cur != __y._M_cur;
	}

	template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
		inline _Val* value_type(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (_Val*) 0; }
	template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
		inline forward_iterator_tag iterator_category(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return forward_iterator_tag(); }
	template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
		inline ptrdiff_t* distance_type(const _Ht_iterator<_Val,_Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (ptrdiff_t*) 0; }

	template <class _Tp>
		class _Stl_prime {
public:
	static const size_t _M_list[28];
	};

	typedef _Stl_prime<bool> _Stl_prime_type;

	template <class _Val, class _Key, class _HF,
		class _ExK, class _EqK, class _All>
		class hashtable {
		typedef hashtable<_Val, _Key, _HF, _ExK, _EqK, _All> _Self;
public:
	typedef _Key key_type;
	typedef _Val value_type;
	typedef _HF hasher;
	typedef _EqK key_equal;
	typedef size_t            size_type;
	typedef ptrdiff_t         difference_type;
	typedef value_type*       pointer;
	typedef const value_type* const_pointer;
	typedef value_type&       reference;
	typedef const value_type& const_reference;
	typedef forward_iterator_tag _Iterator_category;
	hasher hash_funct() const { return _M_hash; }
	key_equal key_eq() const { return _M_equals; }
private:
	typedef _Hashtable_node<_Val> _Node;
private:
	typedef typename _All _M_node_allocator_type;
//	typedef typename _All _M_node_ptr_allocator_type;
//	typedef vector<void*, _M_node_ptr_allocator_type> _BucketVector;
	typedef vector<void*> _BucketVector;
public:
	typedef typename _All allocator_type;
	allocator_type get_allocator() const {
		return (const _M_node_allocator_type&)_M_num_elements;
	}
private:
	hasher                _M_hash;
	key_equal             _M_equals;
	_ExK                  _M_get_key;
	_BucketVector         _M_buckets;
	_STLP_alloc_proxy<size_type, _Node, _M_node_allocator_type>  _M_num_elements;
	const _Node* _M_get_bucket(size_t __n) const { return (_Node*)_M_buckets[__n]; }
public:
	typedef _Const_traits<_Val> __const_val_traits;
	typedef _Nonconst_traits<_Val> __nonconst_val_traits;
	typedef _Ht_iterator<_Val, __const_val_traits,_Key,_HF,_ExK,_EqK, _All> const_iterator;
	typedef _Ht_iterator<_Val, __nonconst_val_traits,_Key,_HF,_ExK,_EqK,_All> iterator;
	friend struct _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>;
	friend struct _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>;
	friend struct _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK, _All>;
public:
	hashtable(size_type __n,
		const _HF&  __hf,
		const _EqK& __eql,
		const _ExK& __ext,
		const allocator_type& __a = allocator_type())
		:
	_M_hash(__hf),
		_M_equals(__eql),
		_M_get_key(__ext),
//		_M_buckets(__a),
		_M_num_elements(__a, (size_type)0)
	{
		_M_initialize_buckets(__n);
	}
	hashtable(size_type __n,
		const _HF&    __hf,
		const _EqK&   __eql,
		const allocator_type& __a = allocator_type())
		:
	_M_hash(__hf),
		_M_equals(__eql),
		_M_get_key(_ExK()),
//		_M_buckets(__a),
		_M_num_elements(__a, (size_type)0)
	{
		_M_initialize_buckets(__n);
	}
	hashtable(const _Self& __ht)
		:
	_M_hash(__ht._M_hash),
		_M_equals(__ht._M_equals),
		_M_get_key(__ht._M_get_key),
		_M_buckets(__ht.get_allocator()),
		_M_num_elements((const _M_node_allocator_type&)__ht._M_num_elements, (size_type)0)
	{
		_M_copy_from(__ht);
	}
	_Self& operator= (const _Self& __ht)
	{
		if (&__ht != this) {
			clear();
			_M_hash = __ht._M_hash;
			_M_equals = __ht._M_equals;
			_M_get_key = __ht._M_get_key;
			_M_copy_from(__ht);
		}
		return *this;
	}
	~hashtable() { clear(); }
	size_type size() const { return _M_num_elements._M_data; }
	size_type max_size() const { return size_type(-1); }
	bool empty() const { return size() == 0; }
	void swap(_Self& __ht)
	{
		_STL_NAMESPACE::swap(_M_hash, __ht._M_hash);
		_STL_NAMESPACE::swap(_M_equals, __ht._M_equals);
		_STL_NAMESPACE::swap(_M_get_key, __ht._M_get_key);
		_M_buckets.swap(__ht._M_buckets);
		_STL_NAMESPACE::swap(_M_num_elements, __ht._M_num_elements);
	}
	iterator begin()
	{
		for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
			if (_M_buckets[__n])
				return iterator((_Node*)_M_buckets[__n], this);
			return end();
	}
	iterator end() { return iterator((_Node*)0, this); }
	const_iterator begin() const
	{
		for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
			if (_M_buckets[__n])
				return const_iterator((_Node*)_M_buckets[__n], this);
			return end();
	}
	const_iterator end() const { return const_iterator((_Node*)0, this); }
	static bool __cdecl _M_equal (const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&,
		const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&);
public:
	size_type bucket_count() const { return _M_buckets.size(); }
	size_type max_bucket_count() const
    { return _Stl_prime_type::_M_list[(int)28 - 1]; }
	size_type elems_in_bucket(size_type __bucket) const
	{
		size_type __result = 0;
		for (_Node* __cur = (_Node*)_M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
			__result += 1;
		return __result;
	}
	pair<iterator, bool> insert_unique(const value_type& __obj)
	{
		resize(_M_num_elements._M_data + 1);
		return insert_unique_noresize(__obj);
	}
	iterator insert_equal(const value_type& __obj)
	{
		resize(_M_num_elements._M_data + 1);
		return insert_equal_noresize(__obj);
	}
	pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
	iterator insert_equal_noresize(const value_type& __obj);
	template <class _InputIterator>
		void insert_unique(_InputIterator __f, _InputIterator __l)
	{
		insert_unique(__f, __l, iterator_category(__f));
	}
	template <class _InputIterator>
		void insert_equal(_InputIterator __f, _InputIterator __l)
	{
		insert_equal(__f, __l, iterator_category(__f));
	}
	template <class _InputIterator>
		void insert_unique(_InputIterator __f, _InputIterator __l,
		const input_iterator_tag &)
	{
		for ( ; __f != __l; ++__f)
			insert_unique(*__f);
	}
	template <class _InputIterator>
		void insert_equal(_InputIterator __f, _InputIterator __l,
		const input_iterator_tag &)
	{
		for ( ; __f != __l; ++__f)
			insert_equal(*__f);
	}
	template <class _ForwardIterator>
		void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
		const forward_iterator_tag &)
	{
		size_type __n = distance(__f, __l);
		resize(_M_num_elements._M_data + __n);
		for ( ; __n > 0; --__n, ++__f)
			insert_unique_noresize(*__f);
	}
	template <class _ForwardIterator>
		void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
		const forward_iterator_tag &)
	{
		size_type __n = distance(__f, __l);
		resize(_M_num_elements._M_data + __n);
		for ( ; __n > 0; --__n, ++__f)
			insert_equal_noresize(*__f);
	}
	reference find_or_insert(const value_type& __obj);
private:
	template <class _KT>
		_Node* _M_find(const _KT& __key) const
	{
		size_type __n = _M_hash(__key)% _M_buckets.size();
		_Node* __first;
		for ( __first = (_Node*)_M_buckets[__n];
		__first && !_M_equals(_M_get_key(__first->_M_val), __key);
		__first = __first->_M_next)
		{}
		return __first;
	}
public:
	template <class _KT>
		iterator find(const _KT& __key)
	{
		return iterator(_M_find(__key), this);
	}
	template <class _KT>
		const_iterator find(const _KT& __key) const
	{
		return const_iterator(_M_find(__key), this);
	}
	size_type count(const key_type& __key) const
	{
		const size_type __n = _M_bkt_num_key(__key);
		size_type __result = 0;
		for (const _Node* __cur = (_Node*)_M_buckets[__n]; __cur; __cur = __cur->_M_next)
			if (_M_equals(_M_get_key(__cur->_M_val), __key))
				++__result;
			return __result;
	}
	pair<iterator, iterator>
		equal_range(const key_type& __key);
	pair<const_iterator, const_iterator>
		equal_range(const key_type& __key) const;
	size_type erase(const key_type& __key);
	void erase(const const_iterator& __it) ;
	void erase(const_iterator __first, const_iterator __last);
	void resize(size_type __num_elements_hint);
	void clear();
public:
	reference _M_insert(const value_type& __obj);
private:
	size_type _M_next_size(size_type __n) const;
	void _M_initialize_buckets(size_type __n)
	{
		const size_type __n_buckets = _M_next_size(__n);
		_M_buckets.reserve(__n_buckets);
		_M_buckets.insert(_M_buckets.end(), __n_buckets, (void*) 0);
		_M_num_elements._M_data = 0;
	}
	size_type _M_bkt_num_key(const key_type& __key) const
	{
		return _M_bkt_num_key(__key, _M_buckets.size());
	}
	size_type _M_bkt_num(const value_type& __obj) const
	{
		return _M_bkt_num_key(_M_get_key(__obj));
	}
	size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
	{
		return _M_hash(__key) % __n;
	}
	size_type _M_bkt_num(const value_type& __obj, size_t __n) const
	{
		return _M_bkt_num_key(_M_get_key(__obj), __n);
	}
	_Node* _M_new_node(const value_type& __obj)
	{
		_Node* __n = _M_num_elements.allocate(1);
		__n->_M_next = 0;
		try {
			_Construct(&__n->_M_val, __obj);
		}
		catch(...) { _M_num_elements.deallocate(__n, 1); throw; };
		return __n;
	}
	void _M_delete_node(_Node* __n)
	{
		_STL_NAMESPACE::_Destroy(&__n->_M_val);
		_M_num_elements.deallocate(__n, 1);
	}
	void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
	void _M_erase_bucket(const size_type __n, _Node* __last);
	void _M_copy_from(const _Self& __ht);
};

template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
inline bool __cdecl
operator==(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __hm1, const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __hm2)
{
	return hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal(__hm1, __hm2);
}
template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
inline bool __cdecl
operator!=(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __hm1, const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __hm2) {
	return !(__hm1 == __hm2);
}
} // end of namespace _STL_NAMESPACE

namespace _STL_NAMESPACE {
	template <class _Tp>
		const size_t _Stl_prime<_Tp>::_M_list[28] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul
		, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul };
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
		class _All>
		_Hashtable_node<_Val>*
		_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_skip_to_next() {
		size_t __bucket = _M_ht->_M_bkt_num(_M_cur->_M_val);
		size_t __h_sz;
		__h_sz = this->_M_ht->bucket_count();
		_Node* __i=0;
		while (__i==0 && ++__bucket < __h_sz)
			__i = (_Node*)_M_ht->_M_buckets[__bucket];
		return __i;
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
		class _All>
		typename hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::size_type
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_next_size(size_type __n) const    {
		const size_type* __first = (const size_type*)_Stl_prime_type::_M_list;
		const size_type* __last =  (const size_type*)_Stl_prime_type::_M_list + (int)28;
		const size_type* pos = __lower_bound(__first, __last, __n, __less((size_type*)0), (ptrdiff_t*)0);
		return (pos == __last ? *(__last - 1) : *pos);
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		bool
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal(
        const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht1,
        const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht2)
	{
		if (__ht1.bucket_count() != __ht2.bucket_count())
			return false;
		for (size_t __n = 0; __n < __ht1.bucket_count(); ++__n) {
			const _Node* __cur1 = __ht1._M_get_bucket(__n);
			const _Node* __cur2 = __ht2._M_get_bucket(__n);
			for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
			__cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
			{}
			if (__cur1 || __cur2)
				return false;
		}
		return true;
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> , bool>
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::insert_unique_noresize(const value_type& __obj)
	{
		const size_type __n = _M_bkt_num(__obj);
		_Node* __first = (_Node*)_M_buckets[__n];
		for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
			if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
				return pair<iterator, bool>(iterator(__cur, this), false);
			_Node* __tmp = _M_new_node(__obj);
			__tmp->_M_next = __first;
			_M_buckets[__n] = __tmp;
			++_M_num_elements._M_data;
			return pair<iterator, bool>(iterator(__tmp, this), true);
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		typename hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::iterator
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::insert_equal_noresize(const value_type& __obj)
	{
		const size_type __n = _M_bkt_num(__obj);
		_Node* __first = (_Node*)_M_buckets[__n];
		for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
			if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
				_Node* __tmp = _M_new_node(__obj);
				__tmp->_M_next = __cur->_M_next;
				__cur->_M_next = __tmp;
				++_M_num_elements._M_data;
				return iterator(__tmp, this);
			}
			_Node* __tmp = _M_new_node(__obj);
			__tmp->_M_next = __first;
			_M_buckets[__n] = __tmp;
			++_M_num_elements._M_data;
			return iterator(__tmp, this);
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		typename hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::reference
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_insert(const value_type& __obj)
	{
		resize(_M_num_elements._M_data + 1);
		size_type __n = _M_bkt_num(__obj);
		_Node* __first = (_Node*)_M_buckets[__n];
		_Node* __tmp = _M_new_node(__obj);
		__tmp->_M_next = __first;
		_M_buckets[__n] = __tmp;
		++_M_num_elements._M_data;
		return __tmp->_M_val;
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		typename hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::reference
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::find_or_insert(const value_type& __obj)
	{
		_Node* __first = _M_find(_M_get_key(__obj));
		if (__first)
			return __first->_M_val;
		else
			return _M_insert(__obj);
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
		_Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> >
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::equal_range(const key_type& __key)
	{
		typedef pair<iterator, iterator> _Pii;
		const size_type __n = _M_bkt_num_key(__key);
		for (_Node* __first = (_Node*)_M_buckets[__n]; __first; __first = __first->_M_next)
			if (_M_equals(_M_get_key(__first->_M_val), __key)) {
				for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
					if (!_M_equals(_M_get_key(__cur->_M_val), __key))
						return _Pii(iterator(__first, this), iterator(__cur, this));
					for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
						if (_M_buckets[__m])
							return _Pii(iterator(__first, this),
							iterator((_Node*)_M_buckets[__m], this));
						return _Pii(iterator(__first, this), end());
			}
			return _Pii(end(), end());
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		pair< _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
		_Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> >
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::equal_range(const key_type& __key) const
	{
		typedef pair<const_iterator, const_iterator> _Pii;
		const size_type __n = _M_bkt_num_key(__key);
		for (const _Node* __first = (_Node*)_M_buckets[__n] ;
		__first;
		__first = __first->_M_next) {
			if (_M_equals(_M_get_key(__first->_M_val), __key)) {
				for (const _Node* __cur = __first->_M_next;
				__cur;
				__cur = __cur->_M_next)
					if (!_M_equals(_M_get_key(__cur->_M_val), __key))
						return _Pii(const_iterator(__first, this),
						const_iterator(__cur, this));
					for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
						if (_M_buckets[__m])
							return _Pii(const_iterator(__first, this),
							const_iterator((_Node*)_M_buckets[__m], this));
						return _Pii(const_iterator(__first, this), end());
			}
		}
		return _Pii(end(), end());
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		typename hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::size_type
		hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const key_type& __key)
	{
		const size_type __n = _M_bkt_num_key(__key);
		_Node* __first = (_Node*)_M_buckets[__n];
		size_type __erased = 0;
		if (__first) {
			_Node* __cur = __first;
			_Node* __next = __cur->_M_next;
			while (__next) {
				if (_M_equals(_M_get_key(__next->_M_val), __key)) {
					__cur->_M_next = __next->_M_next;
					_M_delete_node(__next);
					__next = __cur->_M_next;
					++__erased;
					--_M_num_elements._M_data;
				}
				else {
					__cur = __next;
					__next = __cur->_M_next;
				}
			}
			if (_M_equals(_M_get_key(__first->_M_val), __key)) {
				_M_buckets[__n] = __first->_M_next;
				_M_delete_node(__first);
				++__erased;
				--_M_num_elements._M_data;
			}
		}
		return __erased;
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const const_iterator& __it)
	{
		const _Node* __p = __it._M_cur;
		if (__p) {
			const size_type __n = _M_bkt_num(__p->_M_val);
			_Node* __cur = (_Node*)_M_buckets[__n];
			if (__cur == __p) {
				_M_buckets[__n] = __cur->_M_next;
				_M_delete_node(__cur);
				--_M_num_elements._M_data;
			}
			else {
				_Node* __next = __cur->_M_next;
				while (__next) {
					if (__next == __p) {
						__cur->_M_next = __next->_M_next;
						_M_delete_node(__next);
						--_M_num_elements._M_data;
						break;
					}
					else {
						__cur = __next;
						__next = __cur->_M_next;
					}
				}
			}
		}
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::erase(const_iterator _c_first, const_iterator _c_last)
	{
		iterator& __first = (iterator&)_c_first;
		iterator& __last = (iterator&)_c_last;
		size_type __f_bucket = __first._M_cur ?
			_M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
		size_type __l_bucket = __last._M_cur ?
			_M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
		if (__first._M_cur == __last._M_cur)
			return;
		else if (__f_bucket == __l_bucket)
			_M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
		else {
			_M_erase_bucket(__f_bucket, __first._M_cur, 0);
			for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
				_M_erase_bucket(__n, 0);
			if (__l_bucket != _M_buckets.size())
				_M_erase_bucket(__l_bucket, __last._M_cur);
		}
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::resize(size_type __num_elements_hint)
	{
		const size_type __old_n = _M_buckets.size();
		if (__num_elements_hint > __old_n) {
			const size_type __n = _M_next_size(__num_elements_hint);
			if (__n > __old_n) {
				_BucketVector __tmp(__n, (void*)(0),
					_M_buckets.get_allocator());
				try {
					for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
						_Node* __first = (_Node*)_M_buckets[__bucket];
						while (__first) {
							size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
							_M_buckets[__bucket] = __first->_M_next;
							__first->_M_next = (_Node*)__tmp[__new_bucket];
							__tmp[__new_bucket] = __first;
							__first = (_Node*)_M_buckets[__bucket];
						}
					}
					_M_buckets.swap(__tmp);
				}
				catch(...) {
					for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
						while (__tmp[__bucket]) {
							_Node* __next = ((_Node*)__tmp[__bucket])->_M_next;
							_M_delete_node((_Node*)__tmp[__bucket]);
							__tmp[__bucket] = __next;
						}
					}
					throw;
				}
			}
		}
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
	{
		_Node* __cur = (_Node*)_M_buckets[__n];
		if (__cur == __first)
			_M_erase_bucket(__n, __last);
		else {
			_Node* __next;
			for (__next = __cur->_M_next;
			__next != __first;
			__cur = __next, __next = __cur->_M_next)
				;
			while (__next != __last) {
				__cur->_M_next = __next->_M_next;
				_M_delete_node(__next);
				__next = __cur->_M_next;
				--_M_num_elements._M_data;
			}
		}
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::_M_erase_bucket(const size_type __n, _Node* __last)
	{
		_Node* __cur = (_Node*)_M_buckets[__n];
		while (__cur && __cur != __last) {
			_Node* __next = __cur->_M_next;
			_M_delete_node(__cur);
			__cur = __next;
			_M_buckets[__n] = __cur;
			--_M_num_elements._M_data;
		}
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::clear()
	{
		for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
			_Node* __cur = (_Node*)_M_buckets[__i];
			while (__cur != 0) {
				_Node* __next = __cur->_M_next;
				_M_delete_node(__cur);
				__cur = __next;
			}
			_M_buckets[__i] = 0;
		}
		_M_num_elements._M_data = 0;
	}
	template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
		void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
		::_M_copy_from(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht)
	{
		_M_buckets.clear();
		_M_buckets.reserve(__ht._M_buckets.size());
		_M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (void*) 0);
		try {
			for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
				const _Node* __cur = (_Node*)__ht._M_buckets[__i];
				if (__cur) {
					_Node* __xcopy = _M_new_node(__cur->_M_val);
					_M_buckets[__i] = __xcopy;
					for (_Node* __next = __cur->_M_next;
					__next;
					__cur = __next, __next = __cur->_M_next) {
						__xcopy->_M_next = _M_new_node(__next->_M_val);
						__xcopy = __xcopy->_M_next;
					}
				}
			}
			_M_num_elements._M_data = __ht._M_num_elements._M_data;
		}
		catch(...) { clear(); throw; };
	}
} // end of namespace _STL_NAMESPACE

namespace std {
	template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
		class _EqualKey = equal_to<_Key>,
		class _Alloc = allocator< pair < const _Key, _Tp > > >
		class hash_map
	{
private:
	typedef hashtable < pair < const _Key, _Tp >, _Key, _HashFcn, _Select1st< pair< const _Key, _Tp > >, _EqualKey, _Alloc > _Ht;
	typedef hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
public:
	typedef typename _Ht::key_type key_type;
	typedef _Tp data_type;
	typedef _Tp mapped_type;
	typedef typename _Ht::value_type _value_type;
	typedef typename _Ht::value_type value_type;
	typedef typename _Ht::hasher hasher;
	typedef typename _Ht::key_equal key_equal;
	typedef typename _Ht::size_type size_type;
	typedef typename _Ht::difference_type difference_type;
	typedef typename _Ht::pointer pointer;
	typedef typename _Ht::const_pointer const_pointer;
	typedef typename _Ht::reference reference;
	typedef typename _Ht::const_reference const_reference;
	typedef typename _Ht::iterator iterator;
	typedef typename _Ht::const_iterator const_iterator;
	typedef typename _Ht::allocator_type allocator_type;
	hasher hash_funct() const { return _M_ht.hash_funct(); }
	key_equal key_eq() const { return _M_ht.key_eq(); }
	allocator_type get_allocator() const { return _M_ht.get_allocator(); }
private:
	_Ht _M_ht;
public:
	hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	explicit hash_map(size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	hash_map(size_type __n, const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a = allocator_type())
		: _M_ht(__n, __hf, __eql, __a) {}
	template <class _InputIterator>
		hash_map(_InputIterator __f, _InputIterator __l)
		: _M_ht(100, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql)
		: _M_ht(__n, __hf, __eql, allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a )
		: _M_ht(__n, __hf, __eql, __a)
    { _M_ht.insert_unique(__f, __l); }
public:
	size_type size() const { return _M_ht.size(); }
	size_type max_size() const { return _M_ht.max_size(); }
	bool empty() const { return _M_ht.empty(); }
	void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
	iterator begin() { return _M_ht.begin(); }
	iterator end() { return _M_ht.end(); }
	const_iterator begin() const { return _M_ht.begin(); }
	const_iterator end() const { return _M_ht.end(); }
public:
	pair<iterator,bool> insert(const value_type& __obj)
    { return _M_ht.insert_unique(__obj); }
	template <class _InputIterator>
		void insert(_InputIterator __f, _InputIterator __l)
    { _M_ht.insert_unique(__f,__l); }
	pair<iterator,bool> insert_noresize(const value_type& __obj)
    { return _M_ht.insert_unique_noresize(__obj); }
	iterator find(const key_type& __key) { return _M_ht.find(__key); }
	const_iterator find(const key_type& __key) const { return _M_ht.find(__key); }
	_Tp& operator[](const key_type& __key) {
		iterator __it = _M_ht.find(__key);
		return (__it == _M_ht.end() ?
			_M_ht._M_insert(_value_type(__key, _Tp())).second :
		(*__it).second );
	}
	size_type count(const key_type& __key) const { return _M_ht.count(__key); }
	pair<iterator, iterator> equal_range(const key_type& __key)
    { return _M_ht.equal_range(__key); }
	pair<const_iterator, const_iterator>
		equal_range(const key_type& __key) const
    { return _M_ht.equal_range(__key); }
	size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
	void erase(iterator __it) { _M_ht.erase(__it); }
	void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
	void clear() { _M_ht.clear(); }
	void resize(size_type __hint) { _M_ht.resize(__hint); }
	size_type bucket_count() const { return _M_ht.bucket_count(); }
	size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
	size_type elems_in_bucket(size_type __n) const
    { return _M_ht.elems_in_bucket(__n); }
	static bool __cdecl _M_equal (const _Self& __x, const _Self& __y) {
		return _Ht::_M_equal(__x._M_ht,__y._M_ht);
	}
};
template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
class _EqualKey = equal_to<_Key>,
class _Alloc = allocator< pair < const _Key, _Tp > > >
class hash_multimap
{
private:
	typedef hashtable < pair < const _Key, _Tp >, _Key, _HashFcn, _Select1st< pair< const _Key, _Tp > >, _EqualKey, _Alloc > _Ht;
	typedef hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
public:
	typedef typename _Ht::key_type key_type;
	typedef _Tp data_type;
	typedef _Tp mapped_type;
	typedef typename _Ht::value_type _value_type;
	typedef _value_type value_type;
	typedef typename _Ht::hasher hasher;
	typedef typename _Ht::key_equal key_equal;
	typedef typename _Ht::size_type size_type;
	typedef typename _Ht::difference_type difference_type;
	typedef typename _Ht::pointer pointer;
	typedef typename _Ht::const_pointer const_pointer;
	typedef typename _Ht::reference reference;
	typedef typename _Ht::const_reference const_reference;
	typedef typename _Ht::iterator iterator;
	typedef typename _Ht::const_iterator const_iterator;
	typedef typename _Ht::allocator_type allocator_type;
	hasher hash_funct() const { return _M_ht.hash_funct(); }
	key_equal key_eq() const { return _M_ht.key_eq(); }
	allocator_type get_allocator() const { return _M_ht.get_allocator(); }
private:
	_Ht _M_ht;
public:
	hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	explicit hash_multimap(size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	hash_multimap(size_type __n, const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a = allocator_type())
		: _M_ht(__n, __hf, __eql, __a) {}
	template <class _InputIterator>
		hash_multimap(_InputIterator __f, _InputIterator __l)
		: _M_ht(100, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql)
		: _M_ht(__n, __hf, __eql, allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a )
		: _M_ht(__n, __hf, __eql, __a)
    { _M_ht.insert_equal(__f, __l); }
public:
	size_type size() const { return _M_ht.size(); }
	size_type max_size() const { return _M_ht.max_size(); }
	bool empty() const { return _M_ht.empty(); }
	void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
	iterator begin() { return _M_ht.begin(); }
	iterator end() { return _M_ht.end(); }
	const_iterator begin() const { return _M_ht.begin(); }
	const_iterator end() const { return _M_ht.end(); }
public:
	iterator insert(const value_type& __obj)
    { return _M_ht.insert_equal(__obj); }
	template <class _InputIterator>
		void insert(_InputIterator __f, _InputIterator __l)
    { _M_ht.insert_equal(__f,__l); }
	iterator insert_noresize(const value_type& __obj)
    { return _M_ht.insert_equal_noresize(__obj); }
	iterator find(const key_type& __key) { return _M_ht.find(__key); }
	const_iterator find(const key_type& __key) const
    { return _M_ht.find(__key); }
	size_type count(const key_type& __key) const { return _M_ht.count(__key); }
	pair<iterator, iterator> equal_range(const key_type& __key)
    { return _M_ht.equal_range(__key); }
	pair<const_iterator, const_iterator>
		equal_range(const key_type& __key) const
    { return _M_ht.equal_range(__key); }
	size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
	void erase(iterator __it) { _M_ht.erase(__it); }
	void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
	void clear() { _M_ht.clear(); }
public:
	void resize(size_type __hint) { _M_ht.resize(__hint); }
	size_type bucket_count() const { return _M_ht.bucket_count(); }
	size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
	size_type elems_in_bucket(size_type __n) const
    { return _M_ht.elems_in_bucket(__n); }
	static bool __cdecl _M_equal (const _Self& __x, const _Self& __y) {
		return _Ht::_M_equal(__x._M_ht,__y._M_ht);
	}
};
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
inline bool __cdecl
operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
{
	return hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>::_M_equal(__hm1, __hm2);
}
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
inline bool __cdecl
operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
	return !(__hm1 == __hm2);
}
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
inline bool __cdecl
operator==(const hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, const hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
{
	return hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>::_M_equal(__hm1, __hm2);
}
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
inline bool __cdecl
operator!=(const hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, const hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
	return !(__hm1 == __hm2);
}

} // end of namespace std

//#pragma warning (pop)
//#pragma pack (pop)
//#pragma warning(push)
//#pragma pack(push,8)
//#pragma warning ( disable : 4355 4284  4231 4511 4512 4097 4786 4800 4018 4146 4244 4514 4127 4100 4663)
//#pragma warning ( disable : 4245 4514 4660)
//#pragma once

namespace std {
	template <class _Value, class _HashFcn = hash<_Value>,
		class _EqualKey = equal_to<_Value>,
		class _Alloc = allocator< _Value > >
		class hash_set
	{
private:
	typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
		_EqualKey, _Alloc> _Ht;
	typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
	typedef typename _Ht::iterator _ht_iterator;
public:
	typedef typename _Ht::key_type key_type;
	typedef typename _Ht::value_type value_type;
	typedef typename _Ht::hasher hasher;
	typedef typename _Ht::key_equal key_equal;
	typedef typename _Ht::size_type size_type;
	typedef typename _Ht::difference_type difference_type;
	typedef typename _Ht::pointer         pointer;
	typedef typename _Ht::const_pointer   const_pointer;
	typedef typename _Ht::reference       reference;
	typedef typename _Ht::const_reference const_reference;
	typedef typename _Ht::const_iterator const_iterator;
	typedef const_iterator iterator;
	typedef typename _Ht::allocator_type allocator_type;
	hasher hash_funct() const { return _M_ht.hash_funct(); }
	key_equal key_eq() const { return _M_ht.key_eq(); }
	allocator_type get_allocator() const { return _M_ht.get_allocator(); }
private:
	_Ht _M_ht;
public:
	hash_set()
		: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	explicit hash_set(size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	hash_set(size_type __n, const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a = allocator_type())
		: _M_ht(__n, __hf, __eql, __a) {}
	template <class _InputIterator>
		hash_set(_InputIterator __f, _InputIterator __l)
		: _M_ht(100, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql)
		: _M_ht(__n, __hf, __eql, allocator_type())
    { _M_ht.insert_unique(__f, __l); }
	template <class _InputIterator>
		hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a )
		: _M_ht(__n, __hf, __eql, __a)
    { _M_ht.insert_unique(__f, __l); }
public:
	size_type size() const { return _M_ht.size(); }
	size_type max_size() const { return _M_ht.max_size(); }
	bool empty() const { return _M_ht.empty(); }
	void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
	iterator begin() const { return _M_ht.begin(); }
	iterator end() const { return _M_ht.end(); }
public:
	pair<iterator, bool> insert(const value_type& __obj)
    {
		pair<_ht_iterator, bool> __p = _M_ht.insert_unique(__obj);
		return pair<iterator,bool>(reinterpret_cast<const iterator&>(__p.first), __p.second);
    }
	template <class _InputIterator>
		void insert(_InputIterator __f, _InputIterator __l)
    { _M_ht.insert_unique(__f,__l); }
	pair<iterator, bool> insert_noresize(const value_type& __obj)
	{
		pair<_ht_iterator, bool> __p =
			_M_ht.insert_unique_noresize(__obj);
		return pair<iterator, bool>(__p.first, __p.second);
	}
	template <class _KT>
		iterator find(const _KT& __key) const { return _M_ht.find(__key); }
	size_type count(const key_type& __key) const { return _M_ht.count(__key); }
	pair<iterator, iterator> equal_range(const key_type& __key) const
    { return _M_ht.equal_range(__key); }
	size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
	void erase(iterator __it) { _M_ht.erase(__it); }
	void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
	void clear() { _M_ht.clear(); }
public:
	void resize(size_type __hint) { _M_ht.resize(__hint); }
	size_type bucket_count() const { return _M_ht.bucket_count(); }
	size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
	size_type elems_in_bucket(size_type __n) const
    { return _M_ht.elems_in_bucket(__n); }
	static bool __cdecl _M_equal (const _Self& __x, const _Self& __y) {
		return _Ht::_M_equal(__x._M_ht,__y._M_ht);
	}
};
template <class _Value, class _HashFcn = hash<_Value>,
class _EqualKey = equal_to<_Value>,
class _Alloc = allocator< _Value > >
class hash_multiset
{
private:
	typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
		_EqualKey, _Alloc> _Ht;
	typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
public:
	typedef typename _Ht::key_type key_type;
	typedef typename _Ht::value_type value_type;
	typedef typename _Ht::hasher hasher;
	typedef typename _Ht::key_equal key_equal;
	typedef typename _Ht::size_type size_type;
	typedef typename _Ht::difference_type difference_type;
	typedef typename _Ht::pointer       pointer;
	typedef typename _Ht::const_pointer const_pointer;
	typedef typename _Ht::reference reference;
	typedef typename _Ht::const_reference const_reference;
	typedef typename _Ht::const_iterator const_iterator;
	typedef const_iterator iterator;
	typedef typename _Ht::allocator_type allocator_type;
	hasher hash_funct() const { return _M_ht.hash_funct(); }
	key_equal key_eq() const { return _M_ht.key_eq(); }
	allocator_type get_allocator() const { return _M_ht.get_allocator(); }
private:
	_Ht _M_ht;
public:
	hash_multiset()
		: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	explicit hash_multiset(size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	hash_multiset(size_type __n, const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
		: _M_ht(__n, __hf, __eql, allocator_type()) {}
	hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a)
		: _M_ht(__n, __hf, __eql, __a) {}
	template <class _InputIterator>
		hash_multiset(_InputIterator __f, _InputIterator __l)
		: _M_ht(100, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
		: _M_ht(__n, hasher(), key_equal(), allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf)
		: _M_ht(__n, __hf, key_equal(), allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql)
		: _M_ht(__n, __hf, __eql, allocator_type())
    { _M_ht.insert_equal(__f, __l); }
	template <class _InputIterator>
		hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
		const hasher& __hf, const key_equal& __eql,
		const allocator_type& __a )
		: _M_ht(__n, __hf, __eql, __a)
    { _M_ht.insert_equal(__f, __l); }
public:
	size_type size() const { return _M_ht.size(); }
	size_type max_size() const { return _M_ht.max_size(); }
	bool empty() const { return _M_ht.empty(); }
	void swap(_Self& hs) { _M_ht.swap(hs._M_ht); }
	iterator begin() const { return _M_ht.begin(); }
	iterator end() const { return _M_ht.end(); }
public:
	iterator insert(const value_type& __obj)
    { return _M_ht.insert_equal(__obj); }
	template <class _InputIterator>
		void insert(_InputIterator __f, _InputIterator __l)
    { _M_ht.insert_equal(__f,__l); }
	iterator insert_noresize(const value_type& __obj)
    { return _M_ht.insert_equal_noresize(__obj); }
	template <class _KT>
		iterator find(const _KT& __key) const { return _M_ht.find(__key); }
	size_type count(const key_type& __key) const { return _M_ht.count(__key); }
	pair<iterator, iterator> equal_range(const key_type& __key) const
    { return _M_ht.equal_range(__key); }
	size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
	void erase(iterator __it) { _M_ht.erase(__it); }
	void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
	void clear() { _M_ht.clear(); }
public:
	void resize(size_type __hint) { _M_ht.resize(__hint); }
	size_type bucket_count() const { return _M_ht.bucket_count(); }
	size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
	size_type elems_in_bucket(size_type __n) const
    { return _M_ht.elems_in_bucket(__n); }
	static bool __cdecl _M_equal (const _Self& __x, const _Self& __y) {
		return _Ht::_M_equal(__x._M_ht,__y._M_ht);
	}
};
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
inline bool __cdecl
operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hm1, const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hm2)
{
	return hash_set<_Value,_HashFcn,_EqualKey,_Alloc>::_M_equal(__hm1, __hm2);
}
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
inline bool __cdecl
operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hm1, const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hm2) {
	return !(__hm1 == __hm2);
}
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
inline bool __cdecl
operator==(const hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>& __hm1, const hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>& __hm2)
{
	return hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>::_M_equal(__hm1, __hm2);
}
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
inline bool __cdecl
operator!=(const hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>& __hm1, const hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>& __hm2) {
	return !(__hm1 == __hm2);
}

} // end of namespace std

#pragma warning (pop)
#pragma pack (pop)

#endif /* !_win_hash_map_h_ */
